#include "shearsort.h"

// ------------------- CONSTRUCTORS AND DESTRUCTORS ----------------------
ShearSort::ShearSort(int threadCnt){
    this->threadCnt = threadCnt;
}

ShearSort::~ShearSort(){

}

//-------------------- PUBLIC METHODS ------------------------------------

// Sort items with ShearSort algorithm
// For vertical and horizontal phases use BubbleSort algorithm
void ShearSort::sort(Array * a){
    long itemsCnt = long(a->getCnt()), rowsCnt = sqrt(itemsCnt), colsCnt = itemsCnt / rowsCnt;
    int * items = a->getArray();
    BubbleSort * bs = new BubbleSort();

    if(rowsCnt * colsCnt != itemsCnt) colsCnt++;

    long offset = rowsCnt * colsCnt - itemsCnt;
//    cout << rowsCnt << ", " << colsCnt << ", " << offset << endl;

    #pragma omp parallel
    {
        for(long ii=0;ii<log2(rowsCnt);ii++){
            // Horizontal phase - first row can be incomplete
            #pragma omp for schedule(static, this->threadCnt)
            for(long jj=0;jj<rowsCnt;jj++){
                long start = colsCnt - offset + colsCnt*(jj-1);
                bool desc = ((jj+1)%2 == 0);
//                cout << start << ", " << start + colsCnt - 1 << endl;
                if(jj!=0)
                    bs->sort(items, start, start + colsCnt - 1, desc);
                else
                    bs->sort(items, 0, colsCnt-offset - 1);
    //            cout << start << ", " << start + colsCnt - 1 << endl;
            }

            // Vertical phase
            #pragma omp for schedule(static, this->threadCnt)
            for(long jj=0;jj<colsCnt;jj++){
    //            cout << jj-offset << ", " << itemsCnt-1 << endl;
                bs->sort(items, jj-offset, itemsCnt-1, colsCnt);
    //            cout << jj-offset << ", " << itemsCnt-1 << endl;
            }
        }

        #pragma omp for schedule(static, this->threadCnt)
        for(long jj=0;jj<rowsCnt;jj++){
            long start = colsCnt - offset + colsCnt*(jj-1);
            bool desc = ((jj+1)%2 == 0);
//            cout << start << ", " << start + colsCnt - 1 << endl;
            if(jj!=0)
                bs->sort(items, start, start + colsCnt - 1, desc);
            else
                bs->sort(items, 0, colsCnt-offset - 1);
        }

    }

    delete bs;
}
